from datetime import datetime, date, timedelta, time
from typing import List
import pandas as pd
from ortools.linear_solver import pywraplp as lp

from .base_class import WorkingStaff, DispatchTask, DistanceMatrix, \
    Position, PositionType, WorkingVehicle


REST_POS = Position(pos_type=PositionType.Rest, name="r")
NOON = 720          # 12:00
LUNCH_RANGE = 60    # Lunch time 11:00 ～ 13:00
LUNCH_SPAN = 40     # Lunch break 40min
LUNCH_START = NOON - LUNCH_RANGE
LUNCH_END = NOON + LUNCH_RANGE - LUNCH_SPAN


class DispatchNode:
    NORMAL = 0
    VIRTUAL = 1
    LUNCH = 2

    def __init__(self, 
            task_index: int = None,
            staff_index: int = None,
            task = None,
            staff = None,
            type_id: int = 0,
            start_time_var = None,
            culmu_worktime_var = None,
            rest_var = None,
            ):
        self.task_index = task_index
        self.staff_index = staff_index
        self.type_id = type_id

        self.task = task
        self.staff = staff

        self.planned_start_time = self.task.planned_start_time if task else None 
        self.planned_end_time = self.task.planned_end_time if task else None
        
        self.valid_nexts = []
        self.valid_pres = []

        self.start_time_var = start_time_var
        self.culmu_worktime_var = culmu_worktime_var
        self.rest_var = rest_var

    def __repr__(self):
        if self.type_id == DispatchNode.NORMAL:
            start_time_int = self.start_time_var.solution_value()
            start_time_str = int_to_timestr(start_time_int)
            end_time_int = start_time_int + int(self.task.duration.total_seconds()/60)
            end_time_str = int_to_timestr(end_time_int)
            start_pos = self.task.start_pos
            end_pos = self.task.end_pos
            # cul_worktime_int = int(self.culmu_worktime_var.solution_value())
            return f"F_{self.task_index} T({start_time_str}-{end_time_str}) P({start_pos}-{end_pos})"
        elif self.type_id == DispatchNode.VIRTUAL:
            return f"Staff_{self.staff_index} {str(self.staff.equip)}"
        elif self.type_id == DispatchNode.LUNCH:
            time_int = self.start_time_var.solution_value()
            time_str = int_to_timestr(time_int)
            return f"Lunch: {time_str}"

class DispatchSolver:
    def __init__(self,
            dispatch_dt: datetime,
            distance_matrix: DistanceMatrix,
            staff_list: List[WorkingStaff],
            equip_list: List[WorkingVehicle],
            task_list: List,
            standard,
            rules = {
                "worktime_max": 240,
                "rest_time": 20},
            link_range = 20,
            lunch_range = 20,
            ):
        self._dispatch_dt = dispatch_dt
        self._distance_matrix = distance_matrix
        self._staff_list = staff_list
        self._equip_list = equip_list
        self._task_list = task_list
        self._standard = standard
        self._rules = rules
        self._link_range = link_range
        self._lunch_range = lunch_range

        # Initialize the problem
        # self._solver = lp.Solver("Dispatch Solver", lp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
        self._solver = lp.Solver("Dispatch Solver", lp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)
        # self._solver = lp.Solver("Dispatch Solver", lp.Solver.GUROBI_MIXED_INTEGER_PROGRAMMING)
        
        self.task_cnt = len(task_list)
        self.staff_cnt = len(self._staff_list)
        self._min_workload_var = None
        self._max_workload_var = None

        self._node_matrix = []
        self._rest_node_matrix = []
        self._lunch_node_matrix = []
        self._node_cnt = 0

        self._arc_matrix = {}
        self._arc_cnt = 0

        self._M = 2880

        self._status = None

        # Data preprocessing
        self.sort_task()
        self.equipment_binding()

    @property
    def refer_datetime(self):
        return datetime.combine(
            self._task_list[0].planned_start_time.date(),time(0,0))

    def equipment_binding(self):
        # !! Temporary simple binding
        for i in range(self.staff_cnt):
            staff = self._staff_list[i]
            staff.equip = self._equip_list[i]

    def sort_task(self):
        self._task_list.sort(key=lambda task: task._planned_start_time)

    def construct_network(self):
        print("====================")
        print(f"Total number of flights: {self.task_cnt}")
        print()

        print("====================")
        print("Start generating nodes:")
        # Generate nodes
        # 1. Node per flight_task per staff
        self._node_matrix = [[
                DispatchNode(
                    task_index = i,
                    staff_index = j,
                    task = self._task_list[i],
                    staff = self._staff_list[j],
                    type_id = DispatchNode.NORMAL,
                    start_time_var = self._solver.NumVar(
                        0, 
                        self._solver.Infinity(), 
                        f"Task_{i} Staff_{j} Arrive"),
                    culmu_worktime_var = self._solver.NumVar(
                        0, 
                        self._rules["worktime_max"],
                        f"Task_{i} Staff_{j} Culmulative Work"),
                    rest_var = self._solver.IntVar(
                        0,
                        1,
                        f"Task_{i} Staff_{j} -> Rest"),
                )
                for j in range(self.staff_cnt)] 
                for i in range(self.task_cnt)]

        # 2. Special virtual start/end node for each staff
        self._rest_node_matrix = [{
                "Virtual_Start": DispatchNode(
                    task_index = None,
                    staff_index = j,
                    task = None,
                    staff = self._staff_list[j],
                    type_id=DispatchNode.VIRTUAL,
                    start_time_var = None,
                    culmu_worktime_var=None,
                    rest_var=None
                    ),
                "Virtual_End":  DispatchNode(
                    task_index = None,
                    staff_index = j,
                    task = None,
                    staff = self._staff_list[j],
                    type_id=DispatchNode.VIRTUAL,
                    start_time_var = None,
                    culmu_worktime_var=None,
                    rest_var = None
                    )
            } for j in range(self.staff_cnt)]

        # 3. Special lunch node for each staff
        cnt = 0
        for j in range(self.staff_cnt):
            staff = self._staff_list[j]
            start_work_dt = staff._work_start_time
            end_work_dt = staff._work_end_time
            noon_dt = datetime.combine(self._dispatch_dt.date(), time(hour=12,minute=0))

            if start_work_dt < noon_dt and end_work_dt > noon_dt:
                self._lunch_node_matrix.append(DispatchNode(
                    task_index = None,
                    staff_index = j,
                    task = None,
                    staff = self._staff_list[j],
                    type_id=DispatchNode.LUNCH,
                    start_time_var = self._solver.NumVar(
                        LUNCH_START, LUNCH_END, 
                        f"Staff_{j} Lunch"),
                    culmu_worktime_var = None,
                    rest_var=None
                ))

                cnt += 1
            else:
                self._lunch_node_matrix.append(None)

        # 4. Special work balance variables
        self._min_workload_var = self._solver.NumVar(0, self._solver.Infinity(), "Min Workload")
        self._max_workload_var = self._solver.NumVar(0, self._solver.Infinity(), "Max Workload")
        
        # Node Summary                                 
        print(f"    Variables count: {self.task_cnt * self.staff_cnt * 3 + self.staff_cnt * 2 + cnt + 2}")
        print()
        print("====================")
        print("Start generating arcs:")

        # Generate arcs
        arc_prefix = "    Arcs created: "

        # 1. Arcs between normal dispatch nodes
        cnt = 0
        for j in range(self.staff_cnt):
            for i_1 in range(self.task_cnt - 1):
                # end_index = min(self.task_cnt, i_1 + self._link_range)
                # for i_2 in range(i_1+1, end_index):
                for i_2 in range(i_1+1, self.task_cnt):
                    node_1 = self._node_matrix[i_1][j]
                    node_2 = self._node_matrix[i_2][j]
                    if node_1.task.flight != node_2.task.flight:
                        self._arc_matrix[(node_1, node_2)] = {
                            "arc_var": self._solver.IntVar(0, 1, f"Task_{i_1} Staff_{j} -> Task_{i_2} Staff_{j}"),
                            "runtime": int(self._distance_matrix.get_distance(
                                        node_1.task.end_pos, node_2.task.start_pos))
                        }
                        
                        node_1.valid_nexts.append(node_2)
                        node_2.valid_pres.append(node_1)

                        cnt = self.add_check_cnt(cnt, arc_prefix)
        
        # 2. Arcs between virtual start/end nodes and normal dispatch nodes
        for j in range(self.staff_cnt):
            v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
            v_end_node = self._rest_node_matrix[j]["Virtual_End"]

            # end_index = min(self.task_cnt, self._link_range)
            # for i in range(end_index):
            for i in range(self.task_cnt):
                node = self._node_matrix[i][j]

                self._arc_matrix[(v_start_node, node)] = {
                    "arc_var": self._solver.IntVar(0, 1, f"Start -> Task_{i} Staff_{j}"),
                    "runtime": int(self._distance_matrix.get_distance(
                                REST_POS, node.task.start_pos))
                }
                
                v_start_node.valid_nexts.append(node)
                node.valid_pres.append(v_start_node)

                cnt = self.add_check_cnt(cnt, arc_prefix)
                
            # start_index = max(self.task_cnt - self._link_range, 0)
            # for i in range(start_index, self.task_cnt):
            for i in range(self.task_cnt):
                node = self._node_matrix[i][j]

                self._arc_matrix[(node, v_end_node)] = {
                    "arc_var": self._solver.IntVar(0, 1, f"Task_{i} Staff_{j} -> End"),
                    "runtime": int(self._distance_matrix.get_distance(
                                node.task.end_pos, REST_POS))
                }

                node.valid_nexts.append(v_end_node)
                v_end_node.valid_pres.append(node)

                cnt = self.add_check_cnt(cnt, arc_prefix)

        # 3. Arcs between normal dispatch nodes and lunch nodes
        taskid_before_lunch = 0
        taskid_after_lunch = 0
        for i in range(self.task_cnt):
            task = self._task_list[i]
            start_int = minutes_from_calibr(task.planned_start_time, self.refer_datetime)
            if start_int < LUNCH_START + LUNCH_SPAN:
                taskid_after_lunch += 1
            
            if start_int < LUNCH_END:
                taskid_before_lunch += 1
            else:
                break

        for j in range(self.staff_cnt):
            lunch_node = self._lunch_node_matrix[j]
            if lunch_node:
                for i in range(max(taskid_before_lunch - self._lunch_range, 0), 
                                   taskid_before_lunch):
                    node = self._node_matrix[i][j]
                    self._arc_matrix[(node, lunch_node)] =  {
                        "arc_var": self._solver.IntVar(0, 1, f"Task_{i} Staff_{j} -> Lunch"),
                        "runtime": 0
                    }
                    node.valid_nexts.append(lunch_node)
                    lunch_node.valid_pres.append(node)
                
                for i in range(taskid_after_lunch, 
                               min(taskid_after_lunch + self._lunch_range, self.task_cnt)):
                    node = self._node_matrix[i][j]
                    self._arc_matrix[(lunch_node, node)] =  {
                        "arc_var": self._solver.IntVar(0, 1, f"Lunch -> Task_{i} Staff_{j}"),
                        "runtime": 10
                    }
                    node.valid_pres.append(lunch_node)
                    lunch_node.valid_nexts.append(node)

        # 4. Link v_start and v_end node to handle special case where tasks less than staffs
        for j in range(self.staff_cnt):
            v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
            v_end_node = self._rest_node_matrix[j]["Virtual_End"]
            self._arc_matrix[(v_start_node, v_end_node)] = {
                "arc_var": self._solver.IntVar(0, 1, f"Staff_{j} No Work"),
                "runtime": 0
            }
            v_start_node.valid_nexts.append(v_end_node)
            v_end_node.valid_pres.append(v_start_node)

        print(f"    Arcs created: {cnt}")
        print()

        # print("===Debug Info===")
        # for i in range(self.task_cnt):
        #     for j in range(self.staff_cnt):
        #         node_1 = self._node_matrix[i][j]
        #         node_1_out_arc_cnt = len(node_1.valid_nexts)
        #         node_1_in_arc_cnt = len(node_1.valid_pres)
        #         print(f"{node_1}, out-arc {node_1_out_arc_cnt}, in-arc {node_1_in_arc_cnt}")

    def add_constraints(self):
        print("====================")
        print("Start generating constraints:")
        cnt = 0
        constraint_prefix = "    Constraints created: "

        # 1. Each staff start work from v_start_node and end work at v_end_node
        for j in range(self.staff_cnt):
            v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
            v_end_node = self._rest_node_matrix[j]["Virtual_End"]

            # For each staff, choose one and only one task as his first task
            self._solver.Add(self._solver.Sum(
                [self._arc_matrix[(v_start_node, node)]["arc_var"] for node in v_start_node.valid_nexts]) == 1)

            cnt = self.add_check_cnt(cnt, constraint_prefix)

            # For each staff, choose one and only one task as his last task
            self._solver.Add(self._solver.Sum(
                [self._arc_matrix[(node, v_end_node)]["arc_var"] for node in v_end_node.valid_pres]) == 1)

            cnt = self.add_check_cnt(cnt, constraint_prefix)

        # 2. Network flow conservation
        for i in range(self.task_cnt):
            for j in range(self.staff_cnt):
                node_1 = self._node_matrix[i][j]
                self._solver.Add(
                    self._solver.Sum([self._arc_matrix[(node_1, node_2)]["arc_var"] for node_2 in node_1.valid_nexts]) ==
                    self._solver.Sum([self._arc_matrix[(node_2, node_1)]["arc_var"] for node_2 in node_1.valid_pres]))

                cnt = self.add_check_cnt(cnt, constraint_prefix)

        for j in range(self.staff_cnt):
            node_1 = self._lunch_node_matrix[j]
            if node_1:
                self._solver.Add(
                    self._solver.Sum([self._arc_matrix[(node_2, node_1)]["arc_var"] for node_2 in node_1.valid_pres]) == 1
                )

                self._solver.Add(
                    self._solver.Sum([self._arc_matrix[(node_1, node_2)]["arc_var"] for node_2 in node_1.valid_nexts]) == 1
                )

                cnt = self.add_check_cnt(cnt, constraint_prefix)

        # 3. Task start_time constraints for normal tasks
        for i in range(self.task_cnt):
            for j in range(self.staff_cnt):
                node_1 = self._node_matrix[i][j]
                start_int = minutes_from_calibr(node_1.planned_start_time, self.refer_datetime)
                self._solver.Add(node_1.start_time_var >= start_int)

                cnt = self.add_check_cnt(cnt, constraint_prefix)

        # 4. Runtime and culmulative_worktime constraints between [normal_tasks] + [lunch_tasks]
        for j in range(self.staff_cnt):
            for i_1 in range(self.task_cnt):
                node_1 = self._node_matrix[i_1][j]
                node_1_operation_int = int(node_1.task.duration.total_seconds()/60)
                rest_var = node_1.rest_var

                for node_2 in node_1.valid_nexts:
                    arc_var = self._arc_matrix[(node_1, node_2)]["arc_var"]

                    if node_2.type_id == DispatchNode.NORMAL:
                        run_time_between = self._arc_matrix[(node_1, node_2)]["runtime"]

                        node_2_operation_int = int(node_2.task.duration.total_seconds()/60)

                        # runtime constraint
                        self._solver.Add(
                            node_2.start_time_var - node_1.start_time_var >= 
                            arc_var * (run_time_between + node_1_operation_int) - (1 - arc_var) * self._M +
                            rest_var * self._rules["rest_time"]
                        )

                        cnt = self.add_check_cnt(cnt, constraint_prefix)

                        # culmulative worktime constraint
                        self._solver.Add(
                            node_2.culmu_worktime_var - node_1.culmu_worktime_var >=
                                (node_2.start_time_var + node_2_operation_int) - 
                                (node_1.start_time_var + node_1_operation_int) -
                                self._M * rest_var -
                                self._M * (1 - arc_var)
                        )
                        cnt = self.add_check_cnt(cnt, constraint_prefix)

                        self._solver.Add(
                            node_2.culmu_worktime_var >= (run_time_between + node_2_operation_int) * rest_var
                        )
                        cnt = self.add_check_cnt(cnt, constraint_prefix)
                        
                    if node_2.type_id == DispatchNode.LUNCH:
                        run_time_between = self._arc_matrix[(node_1, node_2)]["runtime"]
                        node_2_operation_int = 0

                        # runtime constraint
                        self._solver.Add(
                            node_2.start_time_var - node_1.start_time_var >= 
                            arc_var * (run_time_between + node_1_operation_int) - (1 - arc_var) * self._M
                        )
                        cnt = self.add_check_cnt(cnt, constraint_prefix)

                        # must rest if LUNCH node is chosen
                        self._solver.Add(rest_var >= arc_var )
                        cnt = self.add_check_cnt(cnt, constraint_prefix)

        for node_1 in self._lunch_node_matrix:
            if node_1:
                for node_2 in node_1.valid_nexts:
                    node_2_operation_int = int(node_2.task.duration.total_seconds()/60)
                    arc_var = self._arc_matrix[(node_1, node_2)]["arc_var"]
                
                    # runtime constraint
                    self._solver.Add(
                        node_2.start_time_var - node_1.start_time_var >= 
                        arc_var * LUNCH_SPAN - (1 - arc_var) * self._M
                    )

                    cnt = self.add_check_cnt(cnt, constraint_prefix)

                    # culmulative worktime constraint
                    self._solver.Add(
                        node_2.culmu_worktime_var >=
                            node_2_operation_int -
                            self._M * (1 - arc_var)
                    )

                    cnt = self.add_check_cnt(cnt, constraint_prefix)
                        
        # 5. Runtime and culmulative_worktime constraints for start/end tasks
        for j in range(self.staff_cnt):
            v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
            v_end_node = self._rest_node_matrix[j]["Virtual_End"]

            work_start_int = minutes_from_calibr(
                    self._staff_list[j]._work_start_time, self.refer_datetime)
            work_end_int = minutes_from_calibr(
                    self._staff_list[j]._work_end_time, self.refer_datetime)

            # !! Temporarily use "REST_POS" now 
            for node_2 in v_start_node.valid_nexts:
                if node_2.type_id != DispatchNode.VIRTUAL:
                    run_time_between = self._arc_matrix[(v_start_node, node_2)]["runtime"]
                    arc_var = self._arc_matrix[(v_start_node, node_2)]["arc_var"]
                    node_2_operation_int = int(node_2.task.duration.total_seconds()/60)

                    # runtime constraint
                    self._solver.Add(
                        node_2.start_time_var >= (run_time_between + work_start_int) * arc_var 
                    )

                    cnt = self.add_check_cnt(cnt, constraint_prefix)

                    # culmulative worktime constraint
                    self._solver.Add(
                        node_2.culmu_worktime_var >= (run_time_between + node_2_operation_int) * arc_var -
                                                    self._M * (1 - arc_var)
                    )

                    cnt = self.add_check_cnt(cnt, constraint_prefix)

            for node_3 in v_end_node.valid_pres:
                if node_2.type_id != DispatchNode.VIRTUAL:
                    run_time_between = self._arc_matrix[(node_3, v_end_node)]["runtime"]
                    arc_var = self._arc_matrix[(node_3, v_end_node)]["arc_var"]
                    rest_var = node_3.rest_var
                    node_3_operation_int = int(node_3.task.duration.total_seconds()/60)
                    latest_time = (work_end_int - run_time_between - node_3_operation_int)

                    # start time constraint
                    self._solver.Add(node_3.start_time_var <= 
                        latest_time * arc_var + (1 - arc_var) * self._M + self._rules["rest_time"] * rest_var)

                    cnt = self.add_check_cnt(cnt, constraint_prefix) 

        # 6. Task covering constraints
        for i in range(self.task_cnt):
            arcs = []
            for j in range(self.staff_cnt):
                node_1 = self._node_matrix[i][j]
                for node_2 in node_1.valid_nexts:
                    arcs.append({
                        "var": self._arc_matrix[(node_1, node_2)]["arc_var"],
                        "staff_index": j,
                    })
            
            cons = self._solver.Constraint(
                self._task_list[i].weight, 
                self._solver.Infinity()
            )

            for arc in arcs:
                cons.SetCoefficient(
                    arc["var"], 
                    self._staff_list[arc["staff_index"]].equip.max_load
                )

            cnt = self.add_check_cnt(cnt, constraint_prefix)

        # 7. Max/Min workload variable constraints
        for j in range(self.staff_cnt):
            min_cons = self._solver.Constraint(-self._solver.Infinity(), 0)
            max_cons = self._solver.Constraint(0, self._solver.Infinity())

            v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
            lunch_node = self._lunch_node_matrix[j]
            for node in v_start_node.valid_nexts:
                operation_int = 0
                if node.task:
                    operation_int = int(node.task.duration.total_seconds()/60)
                total_int = operation_int + self._arc_matrix[(v_start_node, node)]["runtime"]

                min_cons.SetCoefficient(
                    self._arc_matrix[(v_start_node, node)]["arc_var"], -total_int)
                max_cons.SetCoefficient(
                    self._arc_matrix[(v_start_node, node)]["arc_var"], -total_int)

            for node in lunch_node.valid_nexts:
                operation_int = int(node.task.duration.total_seconds()/60)
                total_int = operation_int + self._arc_matrix[(lunch_node, node)]["runtime"]

                min_cons.SetCoefficient(
                    self._arc_matrix[(lunch_node, node)]["arc_var"], -total_int)
                max_cons.SetCoefficient(
                    self._arc_matrix[(lunch_node, node)]["arc_var"], -total_int)

            for i in range(self.task_cnt):
                node_1 = self._node_matrix[i][j]
                for node_2 in node_1.valid_nexts:
                    operation_int = 0
                    if node_2.task:
                        operation_int = int(node_2.task.duration.total_seconds()/60)
                    total_int = operation_int + self._arc_matrix[(node_1, node_2)]["runtime"]

                    min_cons.SetCoefficient(
                        self._arc_matrix[(node_1, node_2)]["arc_var"], -total_int)
                    max_cons.SetCoefficient(
                        self._arc_matrix[(node_1, node_2)]["arc_var"], -total_int)

            min_cons.SetCoefficient(self._min_workload_var, 1)
            max_cons.SetCoefficient(self._max_workload_var, 1)
            cnt = self.add_check_cnt(cnt, constraint_prefix)
            cnt = self.add_check_cnt(cnt, constraint_prefix)

        print(f"{constraint_prefix}{cnt}")
        print()                        

    def set_objective(self):
        obj = self._solver.Objective()
        obj.SetMinimization()

        # Delay time objective
        offset = 0
        for i in range(self.task_cnt):
            for j in range(self.staff_cnt):
                node = self._node_matrix[i][j]
                obj.SetCoefficient(self._node_matrix[i][j].start_time_var, 1)
                offset -= minutes_from_calibr(node.planned_start_time, self.refer_datetime)
        obj.SetOffset(offset) 

        # Work balance objective
        obj.SetCoefficient(self._max_workload_var, 1)
        obj.SetCoefficient(self._min_workload_var, -1)

    def solve(self, num_theads):
        print("=====")
        s_time = datetime.now()
        print(f"Solve start time: {s_time}")

        self._solver.EnableOutput()
        # self._solver.SetNumThreads(num_theads)
        self._solver.SetTimeLimit(1000*60*60*6)
        self._status = self._solver.Solve()
        self.print_result()

        print("=====")
        e_time = datetime.now()
        print(f"Solve end time: {e_time}")
        print(f"Duration: {e_time-s_time}")

    def print_result(self):
        print("===Result Info===")
        print(f"Flights: {self.task_cnt}")

        if self._status  == lp.Solver.OPTIMAL or self._status == lp.Solver.FEASIBLE:
            if self._status == lp.Solver.FEASIBLE:
                print("Find Feasible")
            if self._status == lp.Solver.OPTIMAL:
                print("Find Optimal")

            print()
            print("Solution:")
            print(f"Objective value: {self._solver.Objective().Value()}")
            print(f"Max WorkLoads: {self._max_workload_var.solution_value()}")
            print(f"Min WorkLoads: {self._min_workload_var.solution_value()}")
            print()

            path_list = []
            for rest in self._rest_node_matrix:
                node = rest["Virtual_Start"]
                path = [str(node)+"\n"]
                
                cur_node = node
                culmulative_worktime = 0
                while True:
                    nexts = cur_node.valid_nexts
                    for next_node in nexts:
                        arc_var = self._arc_matrix[(cur_node, next_node)]["arc_var"]
                        rest_var = cur_node.rest_var
                        if arc_var.solution_value() == 1:
                            path.append(f"C({culmulative_worktime})")

                            s_pos, e_pos = REST_POS, REST_POS
                            if cur_node.task:
                                s_pos = cur_node.task.end_pos
                            if next_node.task:
                                e_pos = next_node.task.start_pos

                            run_time = self._distance_matrix.get_distance(s_pos, e_pos)
                            if next_node.type_id == DispatchNode.LUNCH or cur_node.type_id == DispatchNode.LUNCH:
                                run_time = 0
                            culmulative_worktime += run_time

                            node_time = 0
                            if next_node.task:
                                node_time = int(next_node.task.duration.total_seconds()/60)
                            culmulative_worktime += node_time

                            if rest_var and rest_var.solution_value() == 1:
                                path.append(f"Rest")
                                if next_node.type_id == DispatchNode.LUNCH:
                                    culmulative_worktime = 0
                                if next_node.type_id == DispatchNode.NORMAL:
                                    culmulative_worktime = node_time

                            path.append(f"R({str(run_time)})")
                            path.append(str(next_node))
                            cur_node = next_node
                            break

                    if cur_node.type_id == DispatchNode.VIRTUAL:
                        break 

                path_list.append(path[:-1])

            for path in path_list:
                print('---')
                print(" -> ".join(path))

    def add_check_cnt(self, cnt, prefix):
        cnt += 1
        if not (cnt % 10000):
            print(f"{prefix}{cnt}")
        return cnt


def minutes_from_calibr(input_datetime, refer_datetime):
    return int((input_datetime - refer_datetime).total_seconds()/60)

def int_to_timestr(input_int):
    hour = str(int(input_int // 60)).rjust(2, "0")
    minute = str(int(input_int % 60)).rjust(2, "0")
    return f"{hour}:{minute}"


# Archive

# for i in range(self.task_cnt):
#     for j in range(self.staff_cnt):
#         node_1 = self._node_matrix[i][j]
#         for node_2 in node_1.valid_nexts:
#             if node_2.type_id == DispatchNode.NORMAL:
#                 start_int = minutes_from_calibr(node_2.planned_start_time, self.refer_datetime)

#                 self._solver.Add(node_2.start_time_var >= self._arc_matrix[(node_1, node_2)]["arc_var"] *
#                     start_int)

#                 cnt = self.add_check_cnt(cnt, constraint_prefix)

# for j in range(self.staff_cnt):
#     v_start_node = self._rest_node_matrix[j]["Virtual_Start"]
#     for node_2 in v_start_node.valid_nexts:
#         if node_2.type_id != DispatchNode.VIRTUAL:
#             start_int = minutes_from_calibr(node_2.planned_start_time, self.refer_datetime)

#             self._solver.Add(node_2.start_time_var >= self._arc_matrix[(v_start_node, node_2)]["arc_var"] *
#                 start_int)

#             cnt = self.add_check_cnt(cnt, constraint_prefix)